// 题目要求：
// 给一个长度为 n 的数组，如果 0 < a < b < n，求 A[b] - A[a] 的最大值

// 解题思路：
// 贪心，对于任意位置 i，以 i 位置为结尾的最大插值为 A[i] - min(A[0], A[1], ... , A[i - 1])
// 因此只需要遍历一遍数组，用当前元素减前面元素的最小值，得到差值，
// 再求一个差值的最大值

// 解题思路：
// 动态规划，对于任意位置 i，dp[i] 表示 [0, i] 区间的最大差值
// 如果选 i 位置的元素为后面的元素，则 dp[i] = A[i] - min(A[0], A[1], ... , A[i - 1])
// 如果不选 i 位置的元素，则 dp[i] = dp[i - 1]
// 上述两种情况取最大值即可

public class MaxDiff {
    // 解法 1：
    public int getDis (int[] A, int n) {
        int minVal = A[0];
        int diff = 0;

        for(int i = 1; i < n; i++){
            diff = Math.max(diff, Math.max(0, A[i] - minVal));
            minVal = Math.min(minVal, A[i]);
        }

        return diff;
    }
    // 解法 2：
    public int getDis2 (int[] A, int n) {
        int[] dp = new int[n];

        dp[0] = 0;
        dp[1] = (Math.max(A[1] - A[0], 0));

        int min = Math.min(A[0], A[1]);
        for(int i = 2; i < n; i++){
            dp[i] = Math.max(dp[i - 1], Math.max(A[i] - min, 0));
            if(min > A[i]){
                min = A[i];
            }
        }

        return dp[n - 1];
    }
}
